#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 前缀和
// nowcoder:DP34 【模板】前缀和
/*
    思路：
        在输入时计算和，利用数组存储前i个数的和
        在使用时，右边界-(左边界-1)便可得出某一区间内的和
*/
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> arrn(n + 1);
    vector<long long> dp(n + 1);

    // 下标从1开始是因为计算前缀和时，如果要计算[0,2]的和，i-1会变成负数
    for (int i = 1; i <= n; i++)
    {
        // 插入数字
        cin >> arrn[i];

        // 计算前缀和
        // dp[i]表示[1,i]区间内所有元素的和
        dp[i] = arrn[i] + dp[i - 1];
    }
    // 使用前缀和数组
    while (q--)
    {
        int l = 0, r = 0;
        cin >> l >> r;

        cout << dp[r] - dp[l - 1] << endl;
    }

    return 0;
}
// 前缀和
// nowcoder：DP35 【模板】二维前缀和
/*
    思路：
        在一维前缀和的基础上，使用前缀和
        画图：将一个空间从起始位置(1,1)到终点(n,m)分为四块
        所以要求出总面积，公式为A+B+C+D，将它们分割开来进行再次相加减
*/
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> arr(n + 1, vector<int>(m + 1));
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            // 输入
            cin >> arr[i][j];

            // 构建前缀和数组
            // 利用推导出的公式：
            // dp[i][j] = A + B + C + D
            //          = A + (A + B) + (A + C) + D - 2A
            //          = (A + B) + (A + C) + D - A
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
        }
    }

    int x1, y1, x2, y2;
    while (q--)
    {
        // 输入查询参数
        cin >> x1 >> y1 >> x2 >> y2;

        // 利用画图推导出的公式：
        // (A + B + C + D) - (A + B) - (A + C) + A
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
    }

    return 0;
}
// 前缀和
// 724. 寻找数组的中心下标
/*
    思路：
        两个数组，前缀和(从前往后)和后缀和(从后往前)，最后将两个数组进行对比
        注意：
            nums[3] = nums[0] + nums[1] + nums[2]
        即：在两个数组中存放的是下标-1的前缀和 或 下标+1的后缀和
        两个数组中的起始位置(前缀和为0，后缀和为size-1)均为0
*/
class Solution
{
public:
    int pivotIndex(vector<int> &nums)
    {
        int size = nums.size();
        vector<int> f(size), g(size);

        // 预处理前缀和数组和后缀和数组
        for (int i = 1; i < size; i++)
            f[i] = f[i - 1] + nums[i - 1];
        for (int i = size - 2; i >= 0; i--)
            g[i] = g[i + 1] + nums[i + 1];

        // 对比两数组
        for (int i = 0; i < size; i++)
            if (f[i] == g[i])
                return i;

        return -1;
    }
};
// 前缀和
// 238. 除自身以外数组的乘积
// 思路同上
class Solution
{
public:
    vector<int> productExceptSelf(vector<int> &nums)
    {
        int size = nums.size();
        vector<int> f(size), g(size);
        f[0] = g[size - 1] = 1;

        // 预处理前缀积和后缀积
        for (int i = 1; i < size; i++)
            f[i] = f[i - 1] * nums[i - 1];
        for (int i = size - 2; i >= 0; i--)
            g[i] = g[i + 1] * nums[i + 1];

        // 整合数据
        vector<int> dp(size);
        for (int i = 0; i < size; i++)
            dp[i] = f[i] * g[i];

        return dp;
    }
};
// 前缀和
// 560. 和为k的子数组
/*
    思路：
        直接求某段区间内的和是否等于k不好得出结果，时间复杂度太高
        可利用逆向思维：
            设左区间为i，右区间为j，k = sum[j] - sum[i]
            可得出：sum[i] = sum[j] - k
            因此可得出以j位置为结尾的所有的子数组，在[0,j-1]区间内，有多少个前缀和等于sum[j] - k
*/
class Solution
{
public:
    static int subarraySum(vector<int> &nums, int k)
    {
        // 统计前缀和出现的次数
        unordered_map<int, int> hash;
        hash[0] = 1;

        int sum = 0, ret = 0;
        for (auto x : nums)
        {
            // 计算当前位置的前缀和
            sum += x;

            // 统计个数：sum[j] - sum[i] = k
            // sum[i] = sum[j] - k
            if (hash.count(sum - k))
                ret += hash[sum - k];
            hash[sum]++;
        }

        return ret;
    }
};
// 前缀和
// 974. 和可被K整除的子数组
/*
    思路：
        计算时利用同余原理，其余同上
*/
class Solution
{
public:
    int subarraysDivByK(vector<int> &nums, int k)
    {
        unordered_map<int, int> hash;
        hash[0 % k] = 1; // 0 这个数的余数
        int sum = 0, ret = 0;
        for (auto x : nums)
        {
            sum += x;                  // 算出当前位置的前缀和
            int r = (sum % k + k) % k; // 修正后的余数
            if (hash.count(r))         // 统计结果
                ret += hash[r];
            hash[r]++;
        }

        return ret;
    }
};
// 前缀和
// 525. 连续数组
/*
    思路：基本思路同《和为k的子数组》

*/
class Solution
{
public:
    int findMaxLength(vector<int> &nums)
    {
        unordered_map<int, int> hash;
        // 空的前缀的结束下标为 ?1，由于空的前缀的元素和为 0，因此在遍历之前，首先在哈希表中存入键值对 (0,?1)
        hash[0] = -1;

        int sum = 0, ret = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            // 数组内的值为0则该值为-1，为1则正常使用
            sum += (nums[i] == 0 ? -1 : nums[i]);

            // 如果存在，则得出子数组长度
            if (hash.count(sum))
                ret = max(ret, i - hash[sum]);

            // 如果不存在，则将该值插入哈希表
            else
                hash[sum] = i;
        }

        return ret;
    }
};
// 前缀和
// 1314. 矩阵区域和
/*
    思路：
        使用二维前缀和的思路
*/
class Solution
{
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>> &mat, int k)
    {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        // 1. 预处理前缀和数组
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + mat[i - 1][j - 1] - dp[i - 1][j - 1];

        // 2. 使用
        vector<vector<int>> ret(m, vector<int>(n));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                // 边界限制
                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;

                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }

        return ret;
    }
};